#include<bits/stdc++.h>
using namespace std;
using ll=long long;
mt19937 rnd(time(0));
const int N=4e5+5;
int n,d1,d2,d3,d4;
struct FHQ{
	int rt,tot,pro[N],sz[N],ls[N],rs[N];
	ll dat[N],tag[N];
	__int128 sum[N];
	inline void pushdown(int x)
	{
		if(tag[x])
		{
			if(ls[x])sum[ls[x]]+=(__int128)sz[ls[x]]*tag[x],tag[ls[x]]+=tag[x],dat[ls[x]]+=tag[x];
			if(rs[x])sum[rs[x]]+=(__int128)sz[rs[x]]*tag[x],tag[rs[x]]+=tag[x],dat[rs[x]]+=tag[x];
			tag[x]=0;
		}
	}
	inline void pushup(int x)
	{
		sz[x]=sz[ls[x]]+sz[rs[x]]+1;
		sum[x]=sum[ls[x]]+sum[rs[x]]+dat[x];
	}
	inline void Split(int pos,ll xx,int &l,int &r)
	{
		if(!pos)return l=r=0,void();
		pushdown(pos);
		if(dat[pos]<=xx)l=pos,Split(rs[l],xx,rs[l],r);
		else r=pos,Split(ls[r],xx,l,ls[r]);
		pushup(pos);
	}
	inline void Splitsz(int pos,int xx,int &l,int &r)
	{
		if(!pos)return l=r=0,void();
		pushdown(pos);
		if(sz[ls[pos]]+1<=xx)l=pos,Splitsz(rs[l],xx-sz[ls[pos]]-1,rs[l],r);
		else r=pos,Splitsz(ls[r],xx,l,ls[r]);
		pushup(pos);
	}
	inline int Merge(int l,int r)
	{
		if(!l||!r)return l|r;
		pushdown(l),pushdown(r);
		if(pro[l]<pro[r])
		{
			rs[l]=Merge(rs[l],r);
			pushup(l);
			return l;
		}
		else{
			ls[r]=Merge(l,ls[r]);
			pushup(r);
			return r;
		}
	}
	inline ll pre(int x)
	{
		while(ls[x])x=ls[x];
		return dat[x];
	}
	inline ll suf(int x)
	{
		while(rs[x])x=rs[x];
		return dat[x];
	}
	inline void del(int x,ll y)
	{
		int tmp;
		Splitsz(rt,x-1,d1,d2),Splitsz(d2,1,tmp,d2);
		if(d2)tag[d2]-=y,sum[d2]-=1ll*sz[d2]*y,dat[d2]-=y;
		rt=Merge(d1,d2);
	}
	inline void add(int x,ll y)
	{
		Splitsz(rt,x,d1,d2);
		tot++,pro[tot]=rnd()%int(1e9)+1,dat[tot]=sum[tot]=suf(d1)+y,sz[tot]=1;
		if(d2)tag[d2]+=y,sum[d2]+=1ll*sz[d2]*y,dat[d2]+=y;
		rt=Merge(Merge(d1,tot),d2);
	}
	inline ll Get(int x)
	{
		int pos=rt;
		while(1)
		{
			pushdown(pos);
			if(sz[ls[pos]]+1==x)return dat[pos];
			if(sz[ls[pos]]+1<x)x-=sz[ls[pos]]+1,pos=rs[pos];
			else pos=ls[pos];
		}
	}
}T1,T2,T3;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("kte.in","r",stdin);
	freopen("kte.out","w",stdout);
	cin>>n;
	while(n--)
	{
		ll x;
		cin>>x;
		int al=T3.sz[T3.rt];
		T3.Split(T3.rt,x-1,d3,d4);
		if(T3.pre(d4)==x)
		{
			int tmp;
			T3.Splitsz(d4,1,tmp,d4);
			int SZ=T3.sz[d3]+1;
			T3.rt=T3.Merge(d3,d4);
			T1.del(SZ,x),T2.del(al+1-SZ,x);
		}
		else{
			int tmp,SZ=T3.sz[d3];
			T1.add(SZ,x),T2.add(al-SZ,x);
			T3.tot++,T3.pro[T3.tot]=rnd()%int(1e9)+1,T3.dat[T3.tot]=T3.sum[T3.tot]=x,T3.sz[T3.tot]=1;
			T3.rt=T3.Merge(T3.Merge(d3,T3.tot),d4);
		}
		int l=1,r=T3.sz[T3.rt]-1;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(T2.Get(mid)<=T1.Get(mid+1))r=mid-1;
			else l=mid+1;
		}
		__int128 ans=T2.Get(l)-T1.Get(1);
		T2.Splitsz(T2.rt,l,d1,d2);
		ans+=T2.sum[d2],T2.rt=T2.Merge(d1,d2);
		T1.Splitsz(T1.rt,l,d1,d2);
		ans-=T1.sum[d2],T1.rt=T1.Merge(d1,d2);
		cout<<(ll)ans<<'\n';
	}
	return 0;
}

